#!/usr/bin/env python
# -*- coding: utf-8 -*-
from _collections import deque

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x=-1):
        self.val = x
        self.left = None
        self.right = None

        
#广度优先遍历，返回generator object
def bfs_output(root):
    if root is None:
        return;
    q = deque();
    q.append(root)
    while q:
        node = q.popleft();
        yield node.val;
        if node.left is not None:
            q.append(node.left);
        if node.right is not None:
            q.append(node.right);

#深度优先-前序：自己-左-右
def dfs_pre_order(root):
    if root is None:
        return;
    yield root.val;
    for n in dfs_pre_order(root.left): yield n;
    for n in dfs_pre_order(root.right): yield n;
    
#深度优先-中序：左-自己-右
def dfs_in_order(root):
    if root is None:
        return;
    for n in dfs_in_order(root.left): yield n;
    yield root.val;
    for n in dfs_in_order(root.right): yield n;
    
#深度优先-中序：左-右-自己
def dfs_post_order(root):
    if root is None:
        return;
    for n in dfs_post_order(root.left): yield n;
    for n in dfs_post_order(root.right): yield n;
    yield root.val;
    
#获取树的深度
def depth_rec(root):
    if root is None:
        return 0;
    return 1 + max(depth_rec(root.left), depth_rec(root.right));

#左右子树高度差
def depth_distance(root):
    if root is None:
        return 0;
    return abs(depth_rec(root.left)-depth_rec(root.right));

#是否为平衡树：左右子树高度差绝对值不超过1，且都是平衡树
def is_balanced(root):
    return is_balanced_helper(root)[1];
def is_balanced_helper(root):
    if root is None:
        return 0, True;
    depth_left, left_is = is_balanced_helper(root.left);
    depth_right, right_is = is_balanced_helper(root.right);
    dis = depth_left-depth_right;
    cur_depth = max(depth_left, depth_right) + 1;
    return (cur_depth, left_is and right_is and abs(dis)<=1);
    
    